<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>前序遍历 | 悄悄的卷，然后卷死所有人</title>
    <meta name="description" content="这是一个奇怪的地方">
    <link rel="stylesheet" href="/blobview/assets/style.019f39fc.css">
    <link rel="modulepreload" href="/blobview/assets/Home.d05cdc04.js">
    <link rel="modulepreload" href="/blobview/assets/app.a4363fd4.js">
    <link rel="modulepreload" href="/blobview/assets/fe_suanfa_前中后序遍历.md.997426ab.lean.js">
    <link rel="modulepreload" href="/blobview/assets/app.a4363fd4.js">
    <meta name="twitter:title" content="前序遍历 | 悄悄的卷，然后卷死所有人">
    <meta property="og:title" content="前序遍历 | 悄悄的卷，然后卷死所有人">
  </head>
  <body>
    <div id="app"><!--[--><div class="theme"><header class="nav-bar" data-v-675d8756><div class="sidebar-button" data-v-675d8756><svg class="icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z" class></path></svg></div><a class="nav-bar-title" href="/blobview/" aria-label="悄悄的卷，然后卷死所有人, back to home" data-v-675d8756 data-v-4a583abe><!----> 悄悄的卷，然后卷死所有人</a><div class="flex-grow" data-v-675d8756></div><div class="nav" data-v-675d8756><nav class="nav-links" data-v-675d8756 data-v-eab3edfe><!--[--><div class="item" data-v-eab3edfe><div class="nav-link" data-v-eab3edfe data-v-b8818f8c><a class="item" href="/blobview/" data-v-b8818f8c>Home <!----></a></div></div><div class="item" data-v-eab3edfe><div class="nav-dropdown-link" data-v-eab3edfe data-v-56bf3a3f><button class="button" data-v-56bf3a3f><span class="button-text" data-v-56bf3a3f>前端君</span><span class="right button-arrow" data-v-56bf3a3f></span></button><ul class="dialog" data-v-56bf3a3f><!--[--><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/secondary/interviews/network" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>面试八股文</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/algorithm" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>算法大卷</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/errormd/chrome插件开发指南" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>坑你太美</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><!--]--></ul></div></div><div class="item" data-v-eab3edfe><div class="nav-dropdown-link" data-v-eab3edfe data-v-56bf3a3f><button class="button" data-v-56bf3a3f><span class="button-text" data-v-56bf3a3f>稀奇君</span><span class="right button-arrow" data-v-56bf3a3f></span></button><ul class="dialog" data-v-56bf3a3f><!--[--><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/secondary/interviews/network" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>web3</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><!--]--></ul></div></div><div class="item" data-v-eab3edfe><div class="nav-link" data-v-eab3edfe data-v-b8818f8c><a class="item" href="/blobview/b" data-v-b8818f8c>杂谈君 <!----></a></div></div><!--]--><!----><!----></nav></div><!--[--><!--]--></header><aside class="sidebar" data-v-83e92a68><nav class="nav-links nav" data-v-83e92a68 data-v-eab3edfe><!--[--><div class="item" data-v-eab3edfe><div class="nav-link" data-v-eab3edfe data-v-b8818f8c><a class="item" href="/blobview/" data-v-b8818f8c>Home <!----></a></div></div><div class="item" data-v-eab3edfe><div class="nav-dropdown-link" data-v-eab3edfe data-v-56bf3a3f><button class="button" data-v-56bf3a3f><span class="button-text" data-v-56bf3a3f>前端君</span><span class="right button-arrow" data-v-56bf3a3f></span></button><ul class="dialog" data-v-56bf3a3f><!--[--><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/secondary/interviews/network" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>面试八股文</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/algorithm" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>算法大卷</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/errormd/chrome插件开发指南" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>坑你太美</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><!--]--></ul></div></div><div class="item" data-v-eab3edfe><div class="nav-dropdown-link" data-v-eab3edfe data-v-56bf3a3f><button class="button" data-v-56bf3a3f><span class="button-text" data-v-56bf3a3f>稀奇君</span><span class="right button-arrow" data-v-56bf3a3f></span></button><ul class="dialog" data-v-56bf3a3f><!--[--><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/secondary/interviews/network" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>web3</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><!--]--></ul></div></div><div class="item" data-v-eab3edfe><div class="nav-link" data-v-eab3edfe data-v-b8818f8c><a class="item" href="/blobview/b" data-v-b8818f8c>杂谈君 <!----></a></div></div><!--]--><!----><!----></nav><!--[--><!--]--><ul class="sidebar-links" data-v-83e92a68><!--[--><li class="sidebar-link"><a class="sidebar-link-item" href="#前序遍历">前序遍历</a><!----></li><li class="sidebar-link"><a class="sidebar-link-item" href="#代码实现（1）">代码实现（1）</a><!----></li><li class="sidebar-link"><a class="sidebar-link-item" href="#代码实现（优质不占用空间）">代码实现（优质不占用空间）</a><!----></li><li class="sidebar-link"><a class="sidebar-link-item" href="#中序遍历和后续">中序遍历和后续</a><!----></li><li class="sidebar-link"><a class="sidebar-link-item" href="#总结">总结</a><!----></li><!--]--></ul><!--[--><!--]--></aside><div class="sidebar-mask"></div><main class="page" data-v-7eddb2c4><div class="container" data-v-7eddb2c4><!--[--><!--]--><div style="position:relative;" class="content" data-v-7eddb2c4><div><h2 id="前序遍历" tabindex="-1">前序遍历 <a class="header-anchor" href="#前序遍历" aria-hidden="true">#</a></h2><p>假设我们有以下二叉树</p><div class="language-"><pre><code>     1
   /   \
  2     3
 / \   / \
4   5 6   7
</code></pre></div><p>对这棵树进行前序遍历的访问顺序为：1 -&gt; 2 -&gt; 4 -&gt; 5 -&gt; 3 -&gt; 6 -&gt; 7。</p><p><strong>具体实现的过程如下：</strong></p><ol><li>从根节点 1 开始遍历，访问它，输出 1。</li><li>接着遍历左子树，先访问节点 2，输出 2。</li><li>继续遍历 2 的左子树，访问节点 4，输出 4。由于节点 4 没有左右子树，返回到节点 2。</li><li>访问节点 2 的右子树，访问节点 5，输出 5。节点 5 没有左右子树，返回到节点 2。</li><li>返回到节点 1，访问 1 的右子树，访问节点 3，输出 3。</li><li>继续遍历 3 的左子树，访问节点 6，输出 6。节点 6 没有左右子树，返回到节点 3。</li><li>访问节点 3 的右子树，访问节点 7，输出 7。节点 7 没有左右子树，返回到节点 3。</li><li>遍历完成，输出的结果即为 1 2 4 5 3 6 7。</li></ol><h2 id="代码实现（1）" tabindex="-1">代码实现（1） <a class="header-anchor" href="#代码实现（1）" aria-hidden="true">#</a></h2><div class="language-js"><pre><code><span class="token keyword">var</span> res <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token comment">// 返回前序遍历结果</span>
<span class="token keyword">function</span> <span class="token function">preorderTraverse</span><span class="token punctuation">(</span><span class="token parameter">root</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token function">traverse</span><span class="token punctuation">(</span>root<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token keyword">return</span> res<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">// 二叉树遍历函数</span>
<span class="token keyword">function</span> <span class="token function">traverse</span><span class="token punctuation">(</span><span class="token parameter">root</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>root <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
  <span class="token comment">// 前序位置</span>
  res<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>val<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token function">traverse</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>left<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token function">traverse</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>right<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>但你是否能够用「分解问题」的思路，来计算前序遍历的结果？</p><p>换句话说，不要用像 traverse 这样的辅助函数和任何外部变量，单纯用题目给的 preorderTraverse 函数递归解题，你会不会？</p><p>我们知道前序遍历的特点是，根节点的值排在首位，接着是左子树的前序遍历结果，最后是右子树的前序遍历结果：</p><p><img src="https://labuladong.github.io/algo/images/%e4%ba%8c%e5%8f%89%e6%a0%91%e6%94%b6%e5%ae%98/3.jpeg" alt="图片"></p><p><strong>一棵二叉树的前序遍历结果 = 根节点 + 左子树的前序遍历结果 + 右子树的前序遍历结果</strong>。</p><p>所以，你可以这样实现前序遍历算法：</p><h2 id="代码实现（优质不占用空间）" tabindex="-1">代码实现（优质不占用空间） <a class="header-anchor" href="#代码实现（优质不占用空间）" aria-hidden="true">#</a></h2><div class="language-js"><pre><code><span class="token comment">// 定义：输入一棵二叉树的根节点，返回这棵树的前序遍历结果</span>
<span class="token keyword">function</span> <span class="token function">preorderTraverse</span><span class="token punctuation">(</span><span class="token parameter">root</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">var</span> res <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>root <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> res<span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
  <span class="token comment">// 前序遍历的结果，root.val 在第一个</span>
  res<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>val<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment">// 利用函数定义，后面接着左子树的前序遍历结果</span>
  res<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token operator">...</span><span class="token function">preorderTraverse</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>left<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment">// 利用函数定义，最后接着右子树的前序遍历结果</span>
  res<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token operator">...</span><span class="token function">preorderTraverse</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>right<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token keyword">return</span> res<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="中序遍历和后续" tabindex="-1">中序遍历和后续 <a class="header-anchor" href="#中序遍历和后续" aria-hidden="true">#</a></h2><p>中序和后序遍历也是类似的，只要把 add(root.val) 放到中序和后序对应的位置就行了。</p><h2 id="总结" tabindex="-1">总结 <a class="header-anchor" href="#总结" aria-hidden="true">#</a></h2><p>综上，遇到一道二叉树的题目时的通用思考过程是：</p><p>1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现。</p><p>2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值。</p><p>3、无论使用哪一种思维模式，你都要明白二叉树的每一个节点需要做什么，需要在什么时候（前中后序）做。</p></div></div><footer class="page-footer" data-v-7eddb2c4 data-v-fb8d84c6><div class="edit" data-v-fb8d84c6><div class="edit-link" data-v-fb8d84c6 data-v-1ed99556><!----></div></div><div class="updated" data-v-fb8d84c6><!----></div></footer><!----><!--[--><!--]--></div></main></div><!----><!--]--></div>
    <script>__VP_HASH_MAP__ = JSON.parse("{\"fe_algorithm.md\":\"e1054222\",\"fe_errormd_chrome插件开发指南.md\":\"8310a77a\",\"fe_errormd_mysql密码遗忘.md\":\"37b8860e\",\"fe_secondary_javascript_descriptors.md\":\"cd9a7474\",\"fe_secondary_javascript_javascript.md\":\"42853649\",\"fe_secondary_javascript_jicheng.md\":\"1cd0c4dc\",\"fe_secondary_javascript_jscopy.md\":\"66795111\",\"fe_secondary_javascript_js数据类型.md\":\"c6bc851f\",\"fe_secondary_javascript_let const var 的区别.md\":\"685e3545\",\"fe_secondary_javascript_weakmap.md\":\"2a0ba820\",\"fe_secondary_javascript_作用域.md\":\"220cfcf9\",\"fe_secondary_javascript_变量提升.md\":\"b63f20ee\",\"fe_secondary_javascript_闭包.md\":\"5404cbcf\",\"fe_secondary_python_基础知识.md\":\"ae39dc27\",\"fe_secondary_vite_vite杂烩记录.md\":\"aa7cf9a4\",\"fe_secondary_webpack_loader与plugin的不同.md\":\"e2712a7c\",\"fe_secondary_interviews_jstype.md\":\"b3e700ba\",\"fe_secondary_interviews_mianshi.md\":\"218f21c3\",\"fe_secondary_interviews_modular.md\":\"38434f4f\",\"fe_secondary_interviews_network.md\":\"d5842ea6\",\"fe_suanfa_tree树结构.md\":\"d41c852f\",\"fe_suanfa_二分查找.md\":\"28f745d1\",\"fe_suanfa_二叉树.md\":\"836f7969\",\"fe_suanfa_二叉树后序遍历.md\":\"af43c381\",\"fe_suanfa_二叉树展开链表.md\":\"cc410293\",\"fe_suanfa_二叉树最小深度.md\":\"d272316f\",\"fe_suanfa_二叉树的所有路径.md\":\"70f2feac\",\"fe_suanfa_二叉树的最大深度.md\":\"ab1fe25c\",\"fe_suanfa_冒泡排序.md\":\"b91ecca4\",\"fe_suanfa_前中后序遍历.md\":\"997426ab\",\"fe_suanfa_前缀和.md\":\"6ec90ae8\",\"fe_suanfa_区域和检索数组不可变.md\":\"6e447cdb\",\"fe_suanfa_反转数组.md\":\"c28c7d5f\",\"fe_suanfa_将有序数组转换为二叉搜索树.md\":\"6a79c21d\",\"fe_suanfa_差分.md\":\"101d6b54\",\"fe_suanfa_快速排序.md\":\"575fe1af\",\"fe_suanfa_插入排序.md\":\"078511c5\",\"fe_suanfa_滑动窗口.md\":\"08f684ff\",\"fe_suanfa_翻转二叉树.md\":\"1a866015\",\"fe_suanfa_选择排序.md\":\"a25eac11\",\"fe_suanfa_链表反转.md\":\"a642cc7a\",\"fe_web3_ethers_01-hellovitalik.md\":\"162c31f8\",\"fe_web3_ethers_02-合约交互.md\":\"08f30902\",\"fe_web3_ethers_03-发送eth.md\":\"fbf8825d\",\"index.md\":\"64947f2b\"}")</script>
    <script type="module" async src="/blobview/assets/app.a4363fd4.js"></script>
    
  </body>
</html>